import bisect
import collections


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l, s2 = len(s), len(t)

        count = collections.defaultdict(list)
        for i, ch in enumerate(s):
            count[ch].append(i)

        for ch in t:
            if ch not in count:
                return ""

        now = [[i, i] for i in count[t[0]]]

        for j in range(1, s2):
            place = [i for i, ch in enumerate(s) if ch == t[j]]

            nxt = []
            for l, r in now:
                idx = bisect.bisect_right(place, r)
                if idx < len(place):
                    nxt.append([l, place[idx]])
            now = nxt

        ans = ""
        for l, r in now:
            if not ans or r - l + 1 < len(ans):
                ans = s[l:r + 1]
        return ans


if __name__ == "__main__":
    print(Solution().minWindow(s="abcdebdde", t="bde"))  # "bcde"

    # 测试用例1/59
    print(Solution().minWindow(s="jmeqksfrsdcmsiwvaovztaqenprpvnbstl", t="u"))  # ""

    # 测试用例4/59
    print(Solution().minWindow(s="wcbsuiyzacfgrqsqsnodwmxzkz", t="xwqe"))  # ""
